


		STATISTICI LA POLITIE
	       -----------------------

	Ideea de rezolvare este urmatoarea: se alege un punct 0 in interiorul poligonului; se ob-
serva ca semidreptele determinate de punctul O si varfurile poligonului impart planul in n regiuni
distincte (n=numarul de varfuri al poligonului).

	Problema revine deci la:
a) determinarea regiunii careia ii apartine punctul de test A, si
b) verificarea faptului daca A se afla sau nu de aceeasi parte a laturii corespunzatoare regiunii
cu punctul O.

	Daca punctul A se afla de aceeasi parte a laturii cu O, sau daca este chiar pe latura, el
corespunde cerintei initiale. Altfel, el se afla in afara poligonului.
	Mai ramane de rezolvat cazul a). Se observa ca masurile unghiurilor pe care le formeaza
semidreptele (OPi, cu axa absciselor formeaza un sir de valori crescatoare. Punctul a) al rezolva-
rii este echivalent cu gasirea intervalului caruia ii aprtine masura unghiului format de semi-
dreapta (OA cu abscisa. Folosind cautarea binara, acest interval poate fi gasit in O(log N).

	Asadar, complexitatea algoritmului este O(M*logN).